package com.wangjie.datastructuredesign;

import java.util.*;

/**
 * @author jieshao
 * @date 2022/5/25 16:04
 *
 * 380. 常数时间插入、删除和获取随机元素
 */
public class RandomizedSet {
    List<Integer> list;
    Map<Integer, Integer> map;
    Random random;

    public RandomizedSet() {
        this.list = new ArrayList<>();
        this.map = new HashMap<>();
        this.random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        int index = list.size();
        list.add(val);
        map.put(val, index);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int index = map.get(val);
        int last = list.size() - 1;
        list.set(index, list.get(last));
        map.put(list.get(last), index);
        list.remove(last);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        int index = random.nextInt(list.size());
        return list.get(index);
    }
}